package 牛客_面试必刷.Month07.day11;

import java.util.PriorityQueue;

public class 数据流中的中位数 {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->(b - a));
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int count = 0;

    public void Insert(Integer num) {
        if(count++ % 2 == 0){
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }else{
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        }
    }

    public Double GetMedian() {
        if(count % 2 == 0){
            return new Double(minHeap.peek() + maxHeap.peek()) / 2;
        }else{
            return new Double(minHeap.peek());
        }
    }

}
